package Algorithm.interview;

import java.util.PriorityQueue;

/**
 * @Author self
 * @Date 2024/10/7 10:01
 * @Describe top k问题：
 * 从10亿个数中选出最大的1万个数，处理方式：用小顶堆，先用1万个数建立小顶堆，
 * 再把剩余数从小顶堆里过一遍，每次与堆顶元素比较，小顶堆的堆顶元素是最小的，
 * 如果比堆顶元素小就舍弃，如果比堆顶元素大就替换堆顶元素，重新调整为小顶堆，
 * 继续比较直到10亿条数据比完，堆里剩下的就是最大的1万个数。
 *
 * 基于堆（Heap）的解法
 *
 * 思路：使用大小为 K 的最小堆来维护前 K 个最大的元素。堆的大小固定为 K，当堆满时，若当前元素比堆顶元素大，则替换堆顶元素。
 * 时间复杂度：O(n log K)，其中 n 是数组长度，K 是我们需要的前 K 大的元素个数。
 * 空间复杂度：O(K)，需要维护一个大小为 K 的堆。
 */
public class TopK {
    public static int[] findTopK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 最小堆

        // 将前 K 个元素加入堆中
        for (int i = 0; i < k; i++) {
            minHeap.offer(nums[i]);
        }

        // 维护最小堆，如果当前元素比堆顶大，则替换堆顶
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > minHeap.peek()) {
                minHeap.poll();  // 弹出堆顶（最小元素）
                minHeap.offer(nums[i]);  // 加入新的元素
            }
        }

        // 将堆中元素转成数组
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int[] result = findTopK(nums, k);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}
